home *** CD-ROM | disk | FTP | other *** search
/ Gold Medal Software 1 / Gold Medal Software Volume 1 (Gold Medal) (1994).iso / prog / actlib17.arj / STRINGS.ARJ / REGEXP.C < prev    next >
Encoding:
C/C++ Source or Header  |  1993-09-20  |  7.7 KB  |  325 lines
  1. /*  Copyright (C) 1993   Marc Stern  (internet: stern@mble.philips.be)  */
  2.  
  3. #include "strings.h"
  4. #include <stdlib.h>
  5.  
  6.  
  7. /*
  8.    Functions :   matchset
  9.                  match
  10.                  recursexp
  11.                  regexp
  12. */
  13.  
  14.  
  15.  
  16. /***
  17.  *  Function    :  matchset
  18.  *
  19.  *  Description :  Test if a character matches a set expression.
  20.  *
  21.  *  Parameters  :  in    char c          character to be matched
  22.  *                 in    char *pattern   regular expression to match
  23.  *
  24.  *  Parameters  :  in   char   *string
  25.  *
  26.  *  Decisions   :  The following symbols are treated specially:
  27.  *
  28.  *              \  quote next character      -  range of values
  29.  *              ^  non-inclusion (if first character)
  30.  *
  31.  *              ex: aeiou0-9   match a, e, i, o, u, and 0 thru 9
  32.  *                  ^aeiou0-9  match anything but a, e, i, o, u, and 0 thru 9
  33.  *
  34.  *  Return      :  1 or 0
  35.  *
  36.  *  OS/Compiler :  All
  37.  ***/
  38.  
  39. int matchset( char c, char *pattern )
  40.  
  41. {
  42.  const char *begin;
  43.  int match_ok = 1;
  44.  
  45.  if ( ! c ) return 0;
  46.  
  47.  if ( *pattern == '^' )
  48.     {
  49.      match_ok = 0;
  50.      pattern ++;
  51.     }
  52.  
  53.  for ( begin = pattern; *pattern; begin = pattern++ )
  54.     {
  55.      if ( (*pattern == '-') && (pattern != begin) )  /* range */
  56.         {
  57.          pattern ++; if ( *pattern == '\\' ) pattern ++;
  58.          if ( (min(*pattern, *begin) <= c) && (max(*pattern, *begin) >= c) )
  59.             return match_ok;
  60.         }
  61.  
  62.      if ( *pattern == '\\' ) pattern++;
  63.  
  64.      if ( *pattern == c ) return match_ok;
  65.     }
  66.  
  67.  return (! match_ok);
  68. }
  69.  
  70.  
  71.  
  72.  
  73. /***
  74.  *  Function    :  match (internal)
  75.  *
  76.  *  Description :  Returns the number of character of a string matched
  77.  *                 by a one character regular expression.
  78.  *
  79.  *  Decisions   :  The following symbols are treated specially:
  80.  *
  81.  *                 .  any character             \  quote next character
  82.  *                 [] set of characters
  83.  *
  84.  *  Parameters  :  in   char *string    input string to be matched
  85.  *                 in   char *pattern   regular expression to match
  86.  *
  87.  *  Side-effects:  pattern contents will be destroyed.
  88.  *
  89.  *  Return      :  number of character matched by regular expression
  90.  *                 0 if not matched
  91.  *
  92.  *  OS/Compiler :  All
  93.  ***/
  94.  
  95. static int near match( const char *string, char *pattern )
  96. {
  97.  char *ptr;
  98.  int  length = 0;
  99.  
  100.  switch ( *pattern )
  101.  {
  102.   case '.' : *pattern = '\0';
  103.              length = strlen(string);
  104.              break;
  105.  
  106.   case '[' : for ( ptr = ++pattern; *ptr ; ptr ++ )
  107.                 if ( *ptr == ']' )
  108.                    {
  109.                     int i;
  110.                     for ( i = 0; ; i++ )
  111.                        if ( *(ptr - i - 1) != '\\' ) break;
  112.  
  113.                     if ( ! (i % 2) ) break; /* not "\]" */
  114.                    }
  115.  
  116.                 if ( *ptr ) *ptr = '\0';
  117.                 while ( matchset(*string++, pattern) ) length ++;
  118.                 break;
  119.  
  120.   case '\\': pattern ++;
  121.  
  122.   default  : while ( *string++ == *pattern ) length ++;
  123.                       *pattern = '\0';
  124.                       break;
  125.  }
  126.  
  127.  return length;
  128. }
  129.  
  130.  
  131.  
  132.  
  133. /***
  134.  *  Function    :  recursexp
  135.  *
  136.  *  Description :  Returns the number of character of a string matched
  137.  *                 by a regular expression.
  138.  *
  139.  *  Decisions   :  The following symbols are treated specially:
  140.  *
  141.  *                 .  any character             \  quote next character
  142.  *                 *  match zero or more        +  match one or more
  143.  *                 ?  match zero or one         [] set of characters
  144.  *
  145.  *
  146.  *  Parameters  :  in   char *string    input string to be matched
  147.  *                 in   char *pattern   regular expression to match
  148.  *
  149.  *  Return      :  number of character matched by regular expression
  150.  *                 -1 if not matched
  151.  *
  152.  *  OS/Compiler :  All
  153.  ***/
  154.  
  155. int recursexp( const char *string, char *pattern )
  156. {
  157.  int count1, count2 = -1, minone = 0;
  158.  char *pattrn, *ptr;
  159.  
  160.  if ( ! *pattern ) return 0;
  161.  
  162.  ptr = pattrn = strdup( pattern );     /* store it for free() */
  163.  count1 = match( string, pattrn );
  164.  if ( count1 < 0 )
  165.     {
  166.      free( ptr );
  167.      return -1;
  168.     }
  169.  
  170.  while ( *pattrn++ );
  171.  
  172.  switch ( *pattrn )
  173.  {
  174.   case '\0': free( ptr );
  175.              if ( count1 ) return 1;
  176.                       else return -1;
  177.  
  178.   case '*': pattrn++;
  179.             minone = 0;
  180.             break;
  181.  
  182.   case '+': if ( ! count1 )
  183.                {
  184.                 free( ptr );
  185.                 return -1;
  186.                }
  187.              pattrn++;
  188.              break;
  189.  
  190.   case '?': count1 = min( count1, 1 );
  191.             pattrn++;
  192.             break;
  193.  
  194.   default : if ( ! count1 )
  195.                {
  196.                 free( ptr );
  197.                 return -1;
  198.                }
  199.             count1 = 1;
  200.             break;
  201.  }
  202.  
  203.  for ( ; count1 >= 0; count1 -- )
  204.     {
  205.      count2 = recursexp( string + count1, pattrn );
  206.      if ( count2 >= 0 ) break;
  207.     }
  208.  
  209.  free( ptr );
  210.  
  211.  if ( count2 < 0 ) return -1;
  212.  if ( ! count1 && minone ) return -1;
  213.  
  214.  return (count1 + count2);
  215. }
  216.  
  217.  
  218.  
  219.  
  220. /***
  221.  *  Function    :  regexp
  222.  *
  223.  *  Description :  Returns the string matched by a regular expression
  224.  *                 into a string.
  225.  *
  226.  *  Decisions   :  The following symbols are treated specially:
  227.  *
  228.  *                 ^  start of line             $  end of line
  229.  *                 .  any character             \  quote next character
  230.  *                 *  match zero or more        +  match one or more
  231.  *                 ?  match zero or one         [] set of characters
  232.  *        
  233.  *              ex: [aeiou0-9]   match a, e, i, o, u, and 0 thru 9
  234.  *                  [^aeiou0-9]  match anything but a, e, i, o, u, and 0 thru 9
  235.  *
  236.  *  Parameters  :  out   char *outstr    resulting string
  237.  *                 in    char *string    input string in which we search
  238.  *                 in    char *pattern   regular expression to match
  239.  *
  240.  *  Return      :  - NULL if not found
  241.  *                 - pointer to resulting string
  242.  *                 - if ( outstr == NULL ) returns pointer to matched string
  243.  *                   inside 'string'.
  244.  *
  245.  *  OS/Compiler :  All
  246.  ***/
  247.  
  248. char *regexp( char *outstr, const char *string, const char *pattern )
  249. {
  250.  char *ptr, *pattrn;                                                
  251.  int count, begin = 0, end = 0, length;
  252.  
  253.  pattrn = strdup( pattern );
  254.  count = strlen( pattrn ) - 1;
  255.  ptr = pattrn + count;
  256.  if ( (*ptr == '$') )   /* Match end of line ? */
  257.     {
  258.      int i;
  259.      for ( i = 0; i < count ; i++ )
  260.         if ( *(ptr - i - 1) != '\\' ) break;
  261.  
  262.      if ( ! (i % 2) )   /* Match end of line */
  263.         {
  264.          end = 1;
  265.          *ptr = '\0';
  266.         }
  267.     }
  268.  
  269.  ptr = pattrn;  /* store it for free() */
  270.  
  271.  if ( *pattrn == '^' )        /* Match begin of line */
  272.     {
  273.      begin = 1;
  274.      pattrn ++;
  275.     }
  276.  
  277.  for ( length = strlen(string); *string; string++, length-- )
  278.     {
  279.      count = recursexp( string, pattrn );
  280.      if ( begin ) break;  /* only valid as first characters */
  281.      if ( count < 0 ) continue;   /* not found */
  282.      if ( ! end || count == length ) break;
  283.     }
  284.  
  285.  free( ptr );
  286.  
  287.  if ( count < 0 ||
  288.       (end && count != length)
  289.     )
  290.     {
  291.      if ( outstr ) *outstr = '\0';
  292.      return NULL;
  293.     }
  294.  
  295.  if ( outstr )
  296.     {
  297.      strleft( outstr, string, count );
  298.      return outstr;
  299.     }
  300.  
  301.  return (char *)string;
  302. }
  303.  
  304.  
  305. #ifdef TEST
  306.  
  307. #include <stdio.h>
  308. #include <stdlib.h>
  309.  
  310. void main( void )
  311. {
  312.  char string[255], pattern[255], result[255];
  313.  
  314.  for (;;) {
  315.            printf( "\n    String : " );
  316.            if ( ! *gets(string) ) exit(0);
  317.            printf( "    Pattern: " ); gets( pattern );
  318.  
  319.            regexp( result, string, pattern );
  320.            printf( "\n    Result : %s\n\n", result );
  321.           }
  322. }
  323.  
  324. #endif
  325.